package cn.lbd.arithmetic.greedy;

import java.util.*;

/**
 * 假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号
 * <p>
 * 贪心法求解集合覆盖问题：
 * 1. 遍历所有广播电台，找到一个最多未覆盖区域的电台（贪心策略：每次选择一个覆盖地区最多的，每次选择都是最优的）
 * 2. 将这个电台加入到一个集合容器中，并将该电台所覆盖的区域在下一次比较是去掉
 * 3. 重复 1 直到覆盖了所有区域（所有区域集合为空）
 */
public class SetCovering {
    static Map<String, HashSet<String>> map;
    static ArrayList<String> list;

    static {
        map = new HashMap<String, HashSet<String>>();

        HashSet<String> K1 = new HashSet<String>();
        K1.add("北京");
        K1.add("上海");
        K1.add("天津");
        //K1.add("成都");

        HashSet<String> K2 = new HashSet<String>();
        K2.add("广州");
        K2.add("北京");
        K2.add("深圳");

        HashSet<String> K3 = new HashSet<String>();
        K3.add("成都");
        K3.add("上海");
        K3.add("杭州");
        //K3.add("大连");

        HashSet<String> K4 = new HashSet<String>();
        K4.add("上海");
        K4.add("天津");

        HashSet<String> K5 = new HashSet<String>();
        K5.add("杭州");
        K5.add("大连");

        map.put("K1", K1);
        map.put("K2", K2);
        map.put("K3", K3);
        map.put("K4", K4);
        map.put("K5", K5);

        list = new ArrayList<String>();
        list.add("北京");
        list.add("上海");
        list.add("天津");
        list.add("广州");
        list.add("深圳");
        list.add("成都");
        list.add("杭州");
        list.add("大连");
    }

    public static void main(String[] args) {
        List<String> results = new ArrayList<String>();
        Set<String> keys = map.keySet();

        while (list == null || list.size() > 0) {
            int maxCount = 0;
            //<覆盖城市个数，广播编号>
            HashMap<Integer, String> countMap = new HashMap<Integer, String>();
            for (String key : keys) {
                int size = getSize(map.get(key), list);
                countMap.put(size, key);
                if (maxCount < size) {
                    maxCount = size;
                }
            }
            results.add(countMap.get(maxCount));
            //移除list中已加入结果集的电台对应的覆盖城市
            list.removeAll(map.get(countMap.get(maxCount)));
        }
        System.out.println(results.toString());
    }

    public static int getSize(Set<String> target, ArrayList<String> origin) {
        int count = 0;
        for (String varTarget : target) {
            for (String varOrigin : origin) {
                if (varTarget == varOrigin) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}
/**
 * 1. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
 * 2. 比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区
 * 3. 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的
 */
